/*
** Copyright (C) 2009 Joshua Brent Marsh <joshua@icub3d.com>
**  
** This file is part of icub3d-adt
**
** icub3d-adt is free sofware; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 3 of the License, or
** (at your option) any later version.
**  
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**  
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**  
*/

/* $Id: heap.c 42 2009-11-13 18:50:14Z joshua@icub3d.com $ */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <math.h>
#include <string.h>

#include "tree.h"
#include "heap.h"

Heap * 
heap_create (comp_func *comp)
{
  Heap *heap;
  
  heap = malloc (sizeof (Heap));
  if (heap == NULL)
    return NULL;

  heap->comp = comp;
  heap->size = 0;
  heap->min = NULL;
  heap->degrees = NULL;
  heap->roots = list_create_circular ();
  if (heap->roots == NULL)
    {
      free (heap);
      return NULL;
    }

  return heap;
}

void
heap_destroy (Heap *heap, destroy_func dfunc, int nodes)
{
  TreeNode *cur;

  while (list_size (heap->roots) > 0)
    {
      cur = list_remove_first (heap->roots);
      if (nodes)
	tree_node_destroy (cur, dfunc, 1);
    }

  list_destroy (heap->roots, NULL);
  free (heap->degrees);
  free (heap);
}

int
heap_insert (Heap *heap, void *item)
{
  TreeNode *nnode;

  nnode = tree_node_create (NULL, item, 0);
  if (nnode == NULL)
    return 0;

  if (!list_insert_last (heap->roots, nnode))
    {
      free (nnode);
      return 0;
    }

  if (heap->min == NULL)
    heap->min = heap->roots->tail;
  else if (heap->comp (item, ((TreeNode *)heap->min->item)->item) < 0)
    heap->min = heap->roots->tail;

  heap->size++;

  return 1;
}

void * 
heap_find_min (Heap *heap)
{
  return ((TreeNode *)heap->min->item)->item;
}

void
add_children_to_heap (Heap *heap, TreeNode *node)
{
  TreeNode *cur;

  while (list_size (node->children) > 0)
    {
      cur = list_remove_first (node->children);
      list_insert_last (heap->roots, cur);
    }
  tree_node_destroy (node, NULL, 0);
}

void merge_nodes (Heap *heap, ListTraverser *trav, struct list_node **degrees,
		  struct list_node *cur, 
		  struct list_node *found)
{
  struct list_node *min, *max;
  TreeNode *min_node, *max_node;
  if (heap->comp (((TreeNode *)cur->item)->item, 
		  ((TreeNode *)found->item)->item) < 0)
    {
      min = cur;
      max = found;
    }
  else
    {
      min = found;
      max = cur;
    }

  if (trav->cur == max)
    max_node = list_traverser_remove (trav);
  else
    max_node = list_remove_helper (heap->roots, max);

  min_node = (void *)min->item;
  tree_node_add_child (min_node, max_node);

  if (list_size (heap->roots) == 1)
    return;

  degrees[list_size (max_node->children)] = NULL;

  if (degrees[list_size (min_node->children)] == NULL)
    degrees[list_size (min_node->children)] = min;
  else /* We have two with the same degree. */
    {
      merge_nodes (heap, trav, degrees,
		   min, degrees[list_size (min_node->children)]);
    }

}

void * 
heap_extract_min (Heap *heap)
{
  ListTraverser trav;
  TreeNode *min, *ctnode;
  struct list_node *cur, *degree;
  size_t logn;
  void *item;

  if (heap->min == NULL)
    return NULL;

  min = list_remove_helper (heap->roots, heap->min);
  item = min->item;

  heap->size--;

  add_children_to_heap (heap, min);

  if (list_size (heap->roots) == 0)
    {
      heap->min = NULL;
      return item;
    }

  /* Make our array for degrees. */
  logn = ceil (log2 (heap->size)) + 1;
  heap->degrees = realloc (heap->degrees, sizeof (struct list_node *) * logn);
  if (heap->degrees == NULL)
    return NULL; /* Eek, but nothing we can do. */
  memset (heap->degrees, 0, sizeof (struct list_node *) * logn);

  list_traverser_init (&trav, heap->roots);
  while ((ctnode = list_traverser_next (&trav)) != NULL)
    {
      cur = trav.cur;

      /* We got this node before with the same degree. This means we've
	 gone through the circulare reference enough to make sure no two
	 roots have the same degree. */
      if (list_size (heap->roots) == 1)
	break;

      degree = heap->degrees[list_size (ctnode->children)];
      if (degree == cur)
	break;
      else if (degree == NULL)
	heap->degrees[list_size (ctnode->children)] = cur;
      else /* We have two with the same degree. */
	{
	  merge_nodes (heap, &trav, heap->degrees, cur, degree);
	}
    }

  /* Find the min. */
  list_traverser_init (&trav, heap->roots);
  heap->min = heap->roots->head;
  while ((ctnode = list_traverser_next (&trav)) != NULL)
    {
      if (heap->comp (ctnode->item, 
		      ((TreeNode *)heap->min->item)->item) < 0)
	heap->min = trav.cur;   

      if (trav.cur == heap->roots->tail)
	break;
    }

  return item;
}
